洞穴勘测

Time Limit: 10 Sec Memory Limit: 259 MB

Description

辉辉热衷于洞穴勘测。某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 Connect u v 如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 Destroy u v 经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。辉辉希望能随时通过终端机发出指令 Query u v，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

Input

第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

Output

对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

Sample Input

样例输入1 cave.in
　200 5
　Query 123 127
　Connect 123 127
　Query 123 127
　Destroy 127 123
　Query 123 127

样例输入2 cave.in
　3 5
　Connect 1 2
　Connect 3 1
　Query 2 3
　Destroy 1 3
　Query 2 3

Sample Output

样例输出1 cave.out
　No
　Yes
　No

样例输出2 cave.out
　Yes
　No

HINT

100%的数据满足n≤10000, m≤200000

Main idea

若干操作，加入一条边，删去一条边，查询两点是否连通。

Solution

LCT模板题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
using namespace std;

const int ONE=200001;

int n,T;
int u,v;
char ch[10];


int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

namespace LCT
{
    int lc[ONE],rc[ONE],fa[ONE];
    int hasRev[ONE];

    int is_root(int x)
    {
        return (lc[fa[x]]!=x && rc[fa[x]]!=x);
    }

    void tag_rev(int x)
    {
        hasRev[x]^=1;
        swap(lc[x],rc[x]);
    }

    void tag_down(int x)
    {
        if(hasRev[x])
        {
            tag_rev(lc[x]);
            tag_rev(rc[x]);
            hasRev[x]=0;
        }
    }

    void Turn(int x)
    {
        int y=fa[x],z=fa[y];
        int b= x==lc[y]?rc[x]:lc[x];

        fa[x]=z;    fa[y]=x;
        if(b) fa[b]=y;

        if(z)
        {
            if(y==lc[z]) lc[z]=x;
            else
                if(y==rc[z]) rc[z]=x;
        }

        if(x==lc[y]) rc[x]=y,lc[y]=b;
        else
            if(x==rc[y]) lc[x]=y,rc[y]=b;

    }

    void Splay(int x)
    {
        static int anc[ONE];
        int anc_num=0;
        anc[++anc_num]=x;
        for(int i=x;!is_root(i);i=fa[i]) anc[++anc_num]=fa[i];
        while(anc_num>0) tag_down(anc[anc_num--]);

        while(!is_root(x))
        {
            if(!is_root(fa[x]))
            {
                if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) )
                    Turn(fa[x]);
                else Turn(x);
            }
            Turn(x);
        }
    }

    void access(int x)
    {
        for(int p=x,q=0; p; q=p,p=fa[p])
        {
            Splay(p);
            rc[p]=q;
        }
    }

    void make_root(int x)
    {
        access(x);    Splay(x);    tag_rev(x);
    }

    void link(int x,int y)
    {
        make_root(x);    fa[x]=y;
    }

    void cut(int x,int y)
    {
        make_root(x);    access(y);    Splay(y);
        fa[x]=lc[y]=0;
    }

    int PD(int x,int y)
    {
        make_root(x);    access(y);    Splay(y);
        int pd=0;
        for(int i=x;i;i=fa[i])
        {
            if(i==y)
            {
                pd=1;
                break;
            }
        }
        return pd;
    }
}

int main()
{
    n=get();    T=get();
    while(T--)
    {
        scanf("%s",ch);
        u=get();    v=get();
        if(ch[0]=='C') LCT::link(u,v);
        if(ch[0]=='D') LCT::cut(u,v);
        if(ch[0]=='Q')
        {
            int x=LCT::PD(u,v);
            if(!x) printf("No");
            else printf("Yes");
            printf("\n");
        }
    }
}